/*
Date:20210505 20:51PM
key:用例全过但是最后不通过，完全自己想的。
    先写了一个bool判断root下有无p，通过遍历的方法。

    然后主函数判断root下是否同时有p q，如果是则判断左有无pq 右呢 左右递归此函数，都不行，那就是返回root了
    每一次都是扫root下全部 每次root下一层 复杂度应该O(n-logn) 可以通过画图简单分析出
 */
class Solution {
public:
    bool check(TreeNode* root, TreeNode* &p)
    {

        if(root!=NULL)
        {
            
            if(root==p){return 1;}
            else
            {
                return check(root->left,p)||check(root->right,p);
            }
        }
        else{return 0;}
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* &p, TreeNode* &q) 
    {
        if(root!=NULL)
        {
            
            if(check(root, p)&&check(root, q))
            {
                if(check(root->left, p)&&check(root->left, q))
                {
                    
                    return lowestCommonAncestor(root->left, p, q);
                }
                if(check(root->right, p)&&check(root->right, q))
                {
                    
                    return lowestCommonAncestor(root->right, p, q);
                }
                return root;
            }
            else
            {
                
                return NULL;
            }
        }
        return NULL;
    }
};